/*
 * com.future CO.,ltd.
 */

package com.future;

/**
 * Description: 10. ������ʽƥ��(��ˢ���12)
 * ����һ���ַ���?s?��һ���ַ�����?p��������ʵ��һ��֧�� '.'?��?'*'?��������ʽƥ�䡣
 * <p>
 * '.' ƥ�����ⵥ���ַ�
 * '*' ƥ���������ǰ�����һ��Ԫ��
 * ��νƥ�䣬��Ҫ����?����?�ַ���?s�ģ������ǲ����ַ�����
 * <p>
 * ?
 * ʾ�� 1��
 * <p>
 * ���룺s = "aa", p = "a"
 * �����false
 * ���ͣ�"a" �޷�ƥ�� "aa" �����ַ�����
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/regular-expression-matching
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/4/9:15:58
 */
public class Solution_10 {

    public static void main(String[] args) {
        String s = "aa", p = "a";
        s = "aaaaaab";
        p = "a*b";
        s = "aaaaaab";
        p = "a*b*";
        System.out.println(isMatch(s, p));
    }

    // ��ʼ���԰汾��������б���Ż�
    public static boolean isMatch(String str, String exp) {
        if (str == null || exp == null) {
            return false;
        }
        char[] s = str.toCharArray();
        char[] e = exp.toCharArray();
        return isValid(s, e) && process(s, e, 0, 0);
    }

    // str[si.....] �ܲ��ܱ� exp[ei.....]������� true false
    public static boolean process(char[] s, char[] e, int si, int ei) {
        if (ei == e.length) { // exp û�� str��
            // ei��ĩβ�ˣ�si�Ƿ�Ҳ��ĩβ��
            return si == s.length;
        }
        /**
         * exp[ei]�����ַ�
         *
         * ei����һ��λ��ei + 1���ַ�������*
         * �����㺬�壺
         * 1����һ��λ������ֹλ�ã���Ȼû���ַ����������С�*��
         * 2����һ��λ���Ƿ�λ����û�С�*��
         */
        if (ei + 1 == e.length || e[ei + 1] != '*') {
            /**
             * ע�⣺�����Ǳ̨����exp[ei]�����ַ������붼ƥ���ϣ��������false
             *
             * ei + 1 ����'*'
             * str[si] ����� exp[ei] �����ϣ�����si != s.length
             * si == s.lengthʱ�Ѿ�����ֹλ���ˣ�û���ַ���
             */
            boolean result = si != s.length && (e[ei] == s[si] || e[ei] == '.') && process(s, e, si + 1, ei + 1);
            return result;
        }
        /**
         * ע�⣺�����Ǳ̨����exp[ei]�����ַ������붼ƥ���ϣ��������false
         *
         * �ο���Code04_RegularExpressionMatch_2.jpg
         *  exp[ei]�����ַ�
         *  ei + 1λ�õ��ַ�����*!
         * ���1��f(si,ei+2)
         * s=aaaab
         * e=a*aaaab
         * ��ʱ���a*���0��a,��e=aaaab
         * ���2��f(si+1,ei+2)
         * s=aaaab
         * e=a*aaab
         * ��ʱ���a*���1��a,��e=aaaab
         * ���3��f(si+2,ei+2)
         * s=aaaab
         * e=a*aab
         * ��ʱ���a*���2��a,��e=aaaab
         * .....
         */
        while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
            if (process(s, e, si, ei + 2)) {
                return true;
            }
            si++;
        }
        return process(s, e, si, ei + 2);
    }

    public static boolean isValid(char[] s, char[] e) {
        // s�в�����'.' or '*'
        for (int i = 0; i < s.length; i++) {
            if (s[i] == '*' || s[i] == '.') {
                return false;
            }
        }
        // ��ͷ��e[0]������'*'��û�����ڵ�'*'
        for (int i = 0; i < e.length; i++) {
            if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
                return false;
            }
        }
        return true;
    }

}
